package class05

import (
	"container/list"
)

/*
	给定两个字符串，记为 start 和 to ，再给定一个字符串列表list，list中一定包含to list中没有重复
	字符串，所有的字符串都是小写的
	规定：start 每次只能改变一个字符，最终的目标是彻底变成to，但是每次变成新的字符串必须在list中存在。
	请返回所有最短的变换路径
	【举例】
	start = “abc”， end=“cab”， list={“cab”， “acc”， “cbc”， “ccc”， “cbb”， “aab”， “abb”}
	转换路径的方法有很多种，但是所有最短的转换路径如下：
	abc -》 abb -》 aab -》 cab
	abc -》 abb -》 cbb -》 cab
	abc -》 cbc -》 cac -》 cab
	abc -》 cbc -》 cbb -》 cab
	解法及重点：
		该题可以使用图的深度遍历和宽度遍历解决，可以使用图那么重量级
		需要辅助的数据结构：
			1. 邻居表 nexts
				由于都是小写字母，可以将所有可能的邻居通过枚举列出来，并判断是否在list中
			2. 最短距离表 distances
				使用广度优先遍历生成
			3. 使用深度优先遍历，获取到所有的最短的路径
*/
func FindMinPaths(start string, end string, list []string) [][]string {
	list = append(list, start)
	nexts := GetNexts(list)
	distances := GetDistances(start, nexts, list)
	var pathList []string
	var res [][]string
	collect := func(path []string){
		res = append(res, path)
	}

	GetShortestPaths(start, end, distances, nexts, pathList, collect)
	return res
}

// 深度遍历
func GetShortestPaths(
	cur, to string,             // 现在到达的位置， 目标位置
	distance map[string]int,    // 距离map
	nexts map[string][]string,  // nexts 邻居表
	pathList []string,			// 当前路径
	collect func([]string),				// 收集结果
) {
	pathList = append(pathList, cur)
	if to == cur {
		cp := make([]string, len(pathList))
		copy(cp, pathList)
		collect(cp)
	} else {
		for _, next := range nexts[cur] {
			if distance[next] == distance[cur] + 1 {
				GetShortestPaths(next, to, distance, nexts, pathList, collect)
			}
		}
	}
	pathList = pathList[:len(pathList)-1]
}

func GetDistances(start string, nexts map[string][]string, words []string) map[string]int {
	distances := make(map[string]int)
	wordSet := map[string]struct{}{}
	queue := list.New()
	queue.PushBack(start)
	distances[start] = 0
	wordSet[start] = struct{}{}
	for queue.Len() > 0 {
		cur := queue.Remove(queue.Front()).(string)
		for _, next := range nexts[cur] {
			if _, ok := wordSet[next]; !ok {
				queue.PushBack(next)
				wordSet[next] = struct{}{}
				distances[next] = distances[cur] + 1
			}
		}
	}
	return distances
}

func GetNexts(list []string) map[string][]string {
	nexts := make(map[string][]string)
	chars := make([]byte, 26)
	index := 0
	for char := 'a'; char <= 'z'; char++ {
		chars[index] = byte(char)
		index++
	}
	listSet := map[string]struct{}{}
	for _, s := range list {
		listSet[s] = struct{}{}
	}
	var allNext []string
	for _, s := range list {
		allNext = []string{}
		for j := 0; j < len(s); j++ {
			for _, char := range chars {
				if s[j] == char {
					continue
				}
				allNext = append(allNext, GetNext(s, j, char))
			}
		}
		for _, next := range allNext {
			_, ok := listSet[next]
			_, existS := nexts[s]
			if ok && !existS {
				nexts[s] = []string{next}
			} else if ok && existS {
				nexts[s] = append(nexts[s], next)
			}
		}
	}
	return nexts
}

func GetNext(s string, index int, char byte) string {
	var ans string
	curI := 0
	for curI < len(s) {
		if curI != index {
			ans += string(s[curI])
		} else {
			ans += string(char)
		}
		curI++
	}
	return ans
}
